package com.leetcode.Offer;

public class JZ14_I {
    public int cuttingRope(int n) {
        //尽可能去剪长度为3的绳子
        if (n == 2) {
            return 1;
        } else if (n == 3) {
            return 2;
        }
        //绳子长度大于3
        if (n % 3 == 0) {
            return (int) Math.pow(3, n / 3);
        } else if (n % 3 == 1) {
            return (int) Math.pow(3, n / 3 - 1) * 4;
        } else {
            return (int) Math.pow(3, n / 3) * 2;
        }
    }

    //利用动态规划去做
    public int cuttingRope2(int n) {
        if (n == 2) {
            return 1;
        } else if (n == 3) {
            return 2;
        }

        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;

        for (int i = 4; i <= n; i++) {
            int max = 0;
            for (int j = 1; j <= i / 2; j++) {
                int tmp = dp[j] * dp[i - j];
                max = Math.max(max, tmp);
            }
            dp[i] = max;
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(new JZ14_I().cuttingRope2(8));
    }
}
